TRANSPORTATION SCIENCE
Vol. 52, No. 4, July–August 2018, pp. 965–981
http://pubsonline.informs.org/journal/trsc/ ISSN 0041-1655 (print), ISSN 1526-5447 (online)
Optimization Approaches for the Traveling Salesman
Problem with Drone
Niels Agatz,a Paul Bouman,b Marie Schmidta
a Rotterdam School of Management, Erasmus University, 3062 PA Rotterdam, Netherlands; b Econometric Institute, Erasmus University,
3062 PA Rotterdam, Netherlands
Contact: nagatz@rsm.nl, http://orcid.org/0000-0003-3514-201X (NA); bouman@ese.eur.nl, http://orcid.org/0000-0003-4893-4083 (PB);
schmidt2@rsm.nl, http://orcid.org/0000-0001-9563-9955 (MS)
Received: June 25, 2016
Revised: March 31, 2017; April 14, 2017
Accepted: June 22, 2017
Published Online in Articles in Advance:
April 6, 2018
https://doi.org/10.1287/trsc.2017.0791
Copyright: © 2018 INFORMS
Abstract. The fast and cost-efficient home delivery of goods ordered online is logistically
challenging. Many companies are looking for new ways to cross the last mile to their
customers. One technology-enabled opportunity that recently has received much attention
is the use of drones to support deliveries. An innovative last-mile delivery concept in
which a truck collaborates with a drone to make deliveries gives rise to a new variant of
the traveling salesman problem (TSP) that we call the TSP with drone. In this paper, we
model this problem as an integer program and develop several fast route-first, cluster-
second heuristics based on local search and dynamic programming. We prove worst-
case approximation ratios for the heuristics and test their performance by comparing the
solutions to the optimal solutions for small instances. In addition, we apply our heuristics
to several artificial instances with different characteristics and sizes. Our experiments show
that substantial savings are possible with this concept compared to truck-only delivery.
Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2017.0791.
Keywords: traveling salesman problem • vehicle routing • drones • delivery
1. Introduction
In an effort to provide faster and more cost-efficient
delivery of goods ordered online, companies are look-
ing for new technologies to bridge the last mile to their
customers. One technology-driven opportunity that
has recently received much attention is the deployment
of unmanned aerial vehicles, or drones, to support
parcel delivery. An important advantage of a delivery
drone compared to a regular delivery vehicle is that
it can operate without a costly human pilot. Another
advantage is that a drone is fast and can fly over con-
gested roads without delay.
Several companies, including Amazon, Alibaba, and
Google, are currently running practical trials to inves-
tigate the use of drones for parcel delivery (Popper
2013). These trials typically involve multipropeller
drones that can carry parcels of approximately two
kilograms over a range of 20 kilometers. There are
examples of drones that are already used for deliver-
ies in practice, albeit solely in nonurban environments.
DHL Parcel, for instance, recently started operating a
drone delivery service to deliver medications and other
urgently needed goods to one of Germany’s North
Sea islands (Hern 2014). In this example, the drone
is automated but still has to be continuously moni-
tored. Aeronautics experts expect that drones will be
able to fly autonomously and safely in urban environ-
ments within the next decade, based on rapid advances
in obstacle detection and avoidance technology (Nicas
and Bensinger 2015).
While a drone is fast and relatively inexpensive in
terms of costs per mile, there are also some inherent
limitations to its use. The size of the drone puts an
upper limit on the size of the parcels it can carry. Fur-
thermore, a drone cannot carry more than one pack-
age; thus, it has to return to the depot after each deliv-
ery. Since it is battery powered, the range is likely to
remain limited compared to a regular, fuel-based deliv-
ery vehicle. A regular delivery truck, on the other hand,
has a long range and can carry many parcels, but is also
heavy and slow. Table 1 summarizes the complemen-
tary features of the truck and the drone.
One way to extend the effective range and capacity
of a drone is to let it collaborate with a delivery vehi-
cle. AMP Electric Vehicles is working with the Univer-
sity of Cincinnati Department of Aerospace Engineer-
ing on a drone that would be mounted on top of its
electric-powered trucks to help the truck driver make
deliveries (Wohlsen 2014). The 2016 Mercedes-Benz
concept vehicle called the Vision Van also includes
roof-top drones. In this system, the delivery truck and
the drone collaboratively serve all customers. While
the delivery truck moves between different customer
locations to make deliveries, the drone simultaneously
serves another set of customer locations, returning to
the truck after each delivery to pick up another parcel.
965
Agatz, Bouman, and Schmidt: Optimization Approaches for the TSP-D
966 Transportation Science, 2018, vol. 52, no. 4, pp. 965–981, © 2018 INFORMS
Table 1. Complementary Features of Using a Drone or a
Truck for Delivery
Speed Weight Capacity Range
Drone High Light One Short
Truck Low Heavy Many Long
From a transportation planning perspective, this
innovative new concept gives rise to several relevant
planning problems. Even for a single truck and a
single drone, the problem involves both assignment
decisions and routing decisions. Assignment decisions
determine which vehicle, drone or truck will serve
which customers, and routing decisions determine the
sequence in which the customers assigned to each vehi-
cle are visited. We call this variant of the traveling
salesman problem (TSP) the TSP with drone (TSP-D).
Figure 1 provides an illustration of a small example in
which five customer locations need to be served from
the depot. We see that by serving two customer loca-
tions with the drone instead of the truck, we can reduce
the distance traveled by the truck. By this paralleliza-
tion of different delivery tasks, we can also reduce the
total time required to serve all customers.
Since this is a new phenomenon, there is a need for
new models and innovative algorithms to help better
understand the related planning problems and poten-
tial benefits. This paper aims to fill this gap by devel-
oping a new integer programming (IP) formulation as
well as several fast route-first, cluster-second heuristics
based on local search and dynamic programming for
the TSP-D. We prove worst-case approximation ratios
for the heuristics and test their performance by com-
paring the solutions to the optimal solutions for small
instances. In addition, we apply our heuristics to sev-
eral artificial instances with different characteristics
and sizes to investigate the benefits of delivery with
truck and drone over truck-only delivery for various
problem instances.
The main contributions of this paper are as follows:
(1) We develop a new IP model that is able to solve
Figure 1. An Example of a TSP-D SolutionDepot
Truck node
Drone node
Fly arc
Drive arc
instances of up to 12 nodes to optimality, while ear-
lier research did not report optimal solutions. (2) We
provide several new heuristics that are very fast and
provide good solutions, even for large instances. In
particular, we provide a dynamic programming algo-
rithm that is able to find the best assignment of truck
and drone deliveries for any given delivery sequence.
(3) We conduct a theoretical analysis of our heuristics
by giving a (worst case) approximation guarantee and
an experimental comparison of the different variants.
We are the first to compare heuristic solutions to exact
solutions of the TSP-D, whereas earlier work compared
heuristic solutions for the TSP-D to exact solutions of
the TSP. (4) We conduct a numerical study to assess
the performance of a drone delivery system in vari-
ous customer densities, geographic distributions, and
drone speeds.
The remainder of this paper is organized as follows.
In Section 2, we present the related literature. In Sec-
tion 3, we formally define the problem. In Section 4,
we provide some theoretical insights that help us to
develop suitable solution approaches. In Section 5, we
provide an integer programming formulation, and in
Section 6, we propose several heuristics. In Section 7,
we discuss the results from our computational exper-
iments. Finally, we conclude with some directions for
future research in Section 8.
2. Related Literature
There is an extensive body of research on the travel-
ing salesman problem. For an excellent overview of
the recent advancements in this area, see Applegate
et al. (2011).
One variant of the TSP that is conceptually related to
the TSP-D is the covering salesman problem (CSP) as
introduced by Current and Schilling (1989). The CSP
aims to find the shortest tour of a subset of given nodes
such that every node that is not on the tour is within
a predefined covering distance of a node on the tour.
Current and Schilling (1989) propose a heuristic solu-
tion procedure that is based on the set covering prob-
lem. Several generalizations and special cases of the
CSP have been studied in the literature; see, for exam-
ple, Gulczynski, Heath, and Price (2006); Shuttleworth
et al. (2008); Golden et al. (2012); and Behdani and
Smith (2014). Similar to the CSP, in the TSP-D the truck
does not have to visit all nodes. However, in the TSP-D
it is not enough to pass nodes that are not visited by
the truck within a certain distance threshold, but drone
visits have to be scheduled for each such node, and the
truck and drone need to be synchronized.
From this perspective, the TSP-D can be consid-
ered to fall in the class of vehicle routing problems
that require synchronization between vehicles (Drexl
2012). The TSP-D shares some aspects with the truck
and trailer routing problem (TTRP). In this problem, a
Agatz, Bouman, and Schmidt: Optimization Approaches for the TSP-D
Transportation Science, 2018, vol. 52, no. 4, pp. 965–981, © 2018 INFORMS 967
vehicle composed of a truck with a detachable trailer
serves the demand of a set of customers reachable
by truck and trailer or only by the truck without
the trailer. Several heuristics based on the cluster-first,
route-second principle have been proposed to solve the
TTRP, including tabu search (Scheuerer 2006) and sim-
ulated annealing (Lin, Vincent, and Chou 2009). We are
only aware of one paper that uses a route-first, cluster-
second procedure, that by Villegas et al. (2011). Fur-
thermore, for the TTRP, some exact approaches based
on branch-and-cut (Drexl 2014) and branch-and-price
(Drexl 2011) have been studied. The main difference
between the TTRP and the TSP-D is that both the truck
and the drone can separately serve customer locations
in the TSP-D, while the trailer cannot serve customers
without the truck in the TTRP.
The single truck and trailer routing problem with
satellite depots is a special case of the truck and trailer
routing problem in which all customers can be visited
only by the truck without the trailer. Villegas et al.
(2011) introduce a heuristic to solve this problem. More
recently, Belenguer et al. (2016) provided an exact solu-
tion procedure based on a branch-and-cut algorithm
that enabled them to solve problems with up to 50 cus-
tomer locations and 10 satellite depots.
We are aware of two other papers that consider a
combined truck-and-drone delivery system. Murray
and Chu (2015) investigate the “flying sidekick travel-
ing salesman problem,” which is very similar to the
TSP-D. To solve the problem, they propose a mixed
integer programming formulation for two variants of
the problem and consider two simple heuristics, which
we compare to our heuristic approaches in our compu-
tational experiments in Section 7.
Since Murray and Chu (2015) did not obtain opti-
mal solutions using their model formulation, even for
instances with only six nodes, we present a different
formulation to model the TSP-D as an integer program.
Even though our formulation has an exponential
number of variables in the number of customers, it is
more similar to the strong formulation for the regular
TSP used by Applegate et al. (2011). As a result, we
were able to solve instances with up to 12 customers
to optimality. Furthermore, we believe our formulation
to be a good starting point for exact approaches where
variables are generated on the fly, for example, branch-
and-cut-and-price approaches.
Wang, Poikonen, and Golden (2017) study a vehi-
cle routing problem with drones in which a fleet of
trucks, each equipped with a number of drones, deliv-
ers packages to customers. Their main assumptions on
drone capacity, pickup, and delivery are identical to
our assumptions. In contrast to our paper, they do not
develop approaches to find truck-and-drone tours, but
instead focus on deriving worst case bounds for ratios
of the total delivery time of different delivery options.
Their results imply that for our setting, the truck-
only TSP tour takes at most 1 + α as long as the com-
bined truck-and-drone tour, where the speed of the
drone is α times the speed of the truck. In Theorem 1
we extend this result to the setting where drones follow
a different distance metric than the truck.
Apart from the application of the drone as a deliv-
ery vehicle, there are several works on the opera-
tional aspects of using drones for military and civil
surveillance tasks; see, for example, Evers et al. (2014);
Kim, Baik, and Lee (2014); and Valavanis and Vachtse-
vanos (2015).
3. Problem Definition
The TSP-D can be modeled in a graph G  (V, E), where
node v0 represents the depot and n nodes v1 , . . . , vn ,
serve as the customer locations. Let c(e)  c(vi , vj ) and
cd (e)  cd (vi , vj ) be the travel times between vi and vj
of the truck and the drone, respectively.
The drone is typically faster than the truck, i.e.,
cd (e) ≤ c(e). The reason for this is that the drone may
not need to follow the road network, but may be able to
use shortcuts. Moreover, even if the drone is restricted
to following the same road network as the truck
because of safety and privacy regulations, the drone
is not affected by congestion. Note that the definition
of network distances as driving or flying times implies
that the triangle inequality holds for both c and cd .
The objective of the TSP-D is to find the shortest
tour, in terms of time, to serve all customer locations
by either the truck or the drone. We let Vt ⊆ V be the
set of nodes that need to be served by the truck since
they are not suitable for drone delivery.
Throughout our analysis, we make the following
three assumptions:
1. The drone has unit capacity and has to return to
the truck after each delivery.
2. The pickup of parcels from the truck can take
place only at the customer locations; that is, the drone
can land on and depart from the truck only while it is
parked at a customer location or the depot.
3. To simplify notation, we furthermore assume that
the pickup and delivery time of packages by both vehi-
cles can be neglected. We also assume that the recharg-
ing time of the drone can be neglected, for example, by
swapping batteries. We discuss how this assumption
can be relaxed in Section 8.
In the case where battery life of the drone is lim-
ited, we can specify a certain maximum flying distance,
which we will refer to as drone range dmax (and a cor-
responding flight time of tmax) in each flight.
A solution to the TSP-D is hence a truck route R 
(r0  v0 , r1 , . . . , rn  v0) from v0 to v0 together with a
Agatz, Bouman, and Schmidt: Optimization Approaches for the TSP-D
968 Transportation Science, 2018, vol. 52, no. 4, pp. 965–981, © 2018 INFORMS
drone route D  (d0  v0 , d1 , . . . , dm  v0), where all
nodes v ∈ Vt need to be contained in R. The drone
route describes the full path of the drone, including all
customers that are visited by both truck and drone.
We distinguish between the following types of
nodes.
Drone node: A node that is visited by the drone sep-
arated from the truck
Truck node: A node that is visited by the truck sepa-
rated from the drone
Combined node: A node that is visited by both truck
and drone
To compute the time needed for the pair of tours
(R, D), we cannot simply sum up truck and/or drone
driving times since the two vehicles need to be syn-
chronized; i.e., they have to wait for each other at the
combined nodes. Therefore, it is beneficial to introduce
the concept of an operation.
An operation k consists of two combined nodes,
called the start node and end node; at most one drone
node; and a nonnegative number of truck nodes. If the
operation contains a drone node, the drone departs
from the truck at the start node, then serves the drone
node and meets up with the truck again at the end
node. The truck can travel directly from the start node
to the end node or can visit any number of truck nodes
in between. Moreover, the truck can also remain sta-
tionary at the start node for the drone to return. In this
case, the start node is equal to the end node. If the
operation does not contain a drone node, the operation
consists of just one edge between the start node and the
end node. The truck rides from the start node to the
end node while the drone stays parked on the truck.
We call such an operation basic.
Hence, an operation can be described as a pair of
subtours (Rk , Dk ), where Rk is the subsequence of R
starting at the kth combined node of R and up to
and including the (k + 1)th combined node of R. Sim-
ilarly, Dk is the subsequence of D from the kth com-
bined node of D up to and including the (k + 1)th com-
bined node of D. We denote by c(Rk ) : ∑e∈Rk c(e) and
cd (Dk ) : ∑e∈Dk cd (e) the driving time/flying time on
the subtours Rk and Dk , respectively. Note that the sub-
sequence of the drone contains at most two edges for
any feasible solution because we assume that at most
one drone delivery can take place within an operation.
To evaluate the time duration of a solution (R, D)
to the TSP-D, it is convenient to regard (R, D) as
a sequence of operations (o1 , o2 , . . . , ol ) in the above-
described way. In the case that the drone is at least
as fast as the truck between every pair of nodes, the
time duration of an operation ok can be computed as
Figure 2. An Operation with a Combined Node Serving as
the Start Node (1), a Combined Node Serving as the End
Node (4), a Drone Node (3), and a Truck Node (2)21 4
3
3 3
2.5 2.5
t(ok )  max{c(Rk ), cd (Dk )}. In the case that the drone
can be slower than the truck, we have
t(ok ) 



max{c(Rk ), cd (Dk )} if ok contains a
drone node,
c(Rk ) if ok does not contain
a drone node.
(1)
Finally, the overall time needed to serve all customers
using the TSP-D tour (R, D) is
t(R, D) : ∑
k∈K
t(ok ).
Figure 2 provides an illustrative example of an oper-
ation, where the dashed arcs correspond to the path
of the drone and the solid arcs correspond to the path
of the truck. The numbers above the arcs represent the
travel times of the truck and the drone. This operation
has node 1 as the start node, node 3 as the drone node,
and node 2 as the truck node. The time that it takes to
complete this operation is max(6, 5)  6, and the drone
will need to wait for the truck at node 4.
4. Theoretical Insights
Since the TSP-D generalizes the NP-hard Hamiltonian
cycle problem (Karp 1972), the TSP-D is NP-hard. In the
following, we describe some insights into the TSP-D,
which help us to develop suitable solution algorithms
in Sections 5 and 6.
To specify bounds and approximation results, we
express the maximum speedup that can be gained
by using the drone instead of the truck between two
nodes vi and vj by α, that is, α : max{vi , v j }∈E {c(vi , vj )/
cd (vi , vj )}. In this section, we provide the proofs for the
case where the drone is at least as fast as the truck, that
is, cd (vi , vj ) ≤ c(vi , vj ) for all nodes vi , vj to avoid unnec-
essary notation. However, the results also hold if the
drone speed is lower than the truck speed for some pair
of nodes. See the online appendix for details.
In Section 4.1, we start by analyzing how much
we can gain by delivering goods with the truck and
drone instead of only the truck. In Section 4.2, we
prove a lower bound on the optimal solution value
Agatz, Bouman, and Schmidt: Optimization Approaches for the TSP-D
Transportation Science, 2018, vol. 52, no. 4, pp. 965–981, © 2018 INFORMS 969
Figure 3. Two Customers (Circle) That Need to Be Served
from the Depot (Rectangle)v1 v2
1 
of the TSP-D and show that TSP algorithms can be
used as approximation algorithms for the TSP-D. Note
that under the assumption that the truck travel time
between each pair of nodes is a multiple of the drone
travel time between these nodes, these two results fol-
low immediately from the findings in Wang, Poiko-
nen, and Golden (2017), where bounds for delivery
with multiple trucks and multiple drones are given. We
show that these results extend to the case of different
distance metrics for the drone and truck.
Finally, in Section 4.3, we state some properties of
optimal TSP-D solutions that we use for our integer
programming formulation in Section 5.
4.1. Comparing Truck-and-Drone Delivery to
Truck-Only Delivery
The use of a drone in combination with a truck allows
for the parallelization of different delivery operations
and can thereby reduce the total time required to serve
all customers.
Consider the example depicted in Figure 3 with
depot node v0 and two customer nodes v1 and v2 that
need to be served from a central depot location and
could both be served by the drone, i.e., Vt  ú. For this
example, we assume that cd (e)  (1/α)c(e) for all edges
e and a given positive α.
The truck driving time between v0 and v1 is 1, the
truck driving time between v0 and v2 is α, and the truck
driving time between v1 and v2 is 1 + α. The optimal
solution to the TSP-D is to serve v1 with the truck and
serve v2 with the drone, which leads to a total time con-
sumption of 2. However, if only the truck can be used,
i.e., if we solve a TSP, the truck would serve both cus-
tomers, leading to a total time consumption of 2 + 2α.
This provides savings in the total service time of a fac-
tor 1 + α.
Indeed, we show in Theorem 1 that the maximum
savings which can be obtained by employing a drone
are of factor 1 + α.
To prove Theorem 1, we observe that under the
assumption that the drone is at least as fast as the truck,
for any TSP-D tour (R, D) it holds that
t(R, D) ≥ max{c(R), cd (D)}; (2)
i.e., the tour duration of the TSP-D tour is always at
least as long as the driving time of the truck, and at
least as long as the flying time of the drone. Further-
more, denoting by VR and VD the node sets of truck
tour R and drone tour D, we can specify the follow-
ing lower bound on the length of the drone tour in an
optimal TSP-D tour.
Lemma 1. Let (R, D) be a TSP-D tour. Then
c(D) ≥ 2 · ∑
v∈VD\VR
min
w∈VR
c(v, w). (3)
Proof.
c(D)  ∑
e∈ED
c(e) ≥ ∑
e∈ED\ER
c(e) ≥ 2 · ∑
v∈VD\VR
min
w∈VR
c(v, w).
The last inequality holds because every operation con-
tains at most one drone node; i.e., the drone visits a
combined node in VR ∩ VD before and after visiting a
drone node in VD\VR. 
Theorem 1. An optimal solution to the TSP is a (1 + α)-
approximation to the TSP-D.
Proof. Here, we prove this result only for the case
cd (vi , vj ) ≤ c(vi , vj ) for all nodes vi , vj . A proof for the
general setting is given in the online appendix. Let
(R∗ , D∗) be an optimal solution to the TSP-D, and let
RTSP be an optimal solution to the TSP.
From (R∗ , D∗) we can construct a TSP tour R in the
following way: Start with R∗. For every drone node
v ∈ VD∗ , we pick the node w ∈ VR∗ that is closest to v
with respect to the driving time c and insert arcs (w, v)
and (v, w) into the tour. Then we have
c(RTSP) ≤ c(R)  c(R∗) + 2 · ∑
v∈VD∗ \VR∗
min
w∈VR∗
c(v, w).
Using (3) we conclude
c(RTSP) ≤ c(R∗) + c(D∗). (4)
Furthermore, using (2) we obtain
t(R∗ , D∗) ≥ max{c(R∗), cd (D∗)}
≥ max
{
c(R∗), 1
α c(D∗)
}
, (5)
where the last inequality follows from the definition
of α.
Combining (4) and (5) we obtain
t(R∗ , D∗) ≥ max
{
c(RTSP) − c(D∗), 1
α c(D∗)
}
≥ c(RTSP)
1 + α .
The last inequality follows from maxy∈+ {c(R∗) − y,
(1/α)y} is minimal if c(R∗) − y  (1/α)y. We conclude
that
t(RTSP , RTSP)  c(RTSP) ≤ (1 + α)t(R∗ , D∗). 
This result proves that the maximum gain we can
obtain by employing the truck and drone together is of
factor 1+ α, and we have seen in the example in Figure 3
that this bound is tight. Note that for the case where
truck speed and drone speed are related as cd (e) 
αc(e) for all edges e, this result is a special case of The-
orem 4 in Wang, Poikonen, and Golden (2017), which